home *** CD-ROM | disk | FTP | other *** search
/ Aminet 28 / Aminet 28 (1998)(GTI - Schatztruhe)[!][Dec 1998].iso / Aminet / dev / c / qtools0.2-src.lha / src / libqsys / TDCS.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-09-09  |  11.6 KB  |  313 lines
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include "TDCS.h"
  4.  
  5. /*
  6.  * =================================================================
  7.  * statistical encoder
  8.  * =================================================================
  9.  */
  10. void cremate(void) {
  11. }
  12.  
  13. /*
  14.  * =================================================================
  15.  * lz77 preprocessor
  16.  * =================================================================
  17.  */
  18.  
  19. void ArrayClear(register struct hashroot *Array __asm__("a0")) {
  20.   bzero(Array, LOOKUP_SIZE * sizeof(struct hashroot));
  21. }
  22.  
  23. int annihilate(register int inSize __asm__ ("d0"),
  24.            register unsigned char *inMem __asm__ ("a0"),
  25.            register int outSize __asm__ ("d1"),
  26.            register unsigned char *outMem __asm__ ("a1"),
  27.            int Mode) {
  28.   register unsigned char *pasteMem;
  29. #define    parseMem    inMem
  30.   register struct hashroot *Array;
  31.   struct ExecBase *SysBase;
  32.   int indexPos;
  33.   unsigned int index;
  34.   unsigned int *indexMem;
  35.   void *memPool;
  36.  
  37.   if(!(Array = malloc(LOOKUP_SIZE * sizeof(struct hashroot))))
  38.     return ERROR_LESSMEM;
  39.  
  40.   ArrayClear(Array);
  41.  
  42.   pasteMem = outMem;
  43.   outSize = inSize;                        /* do not grow size */
  44.   outMem += outSize;                        /* last valid output */
  45.  
  46.   indexMem = ((unsigned int *)pasteMem)++;            /* store the inde before each block */
  47.   index = 0;
  48.   indexPos = INDEX_LENGTH - 1;
  49.  
  50.   while (inSize > 0) {
  51.     unsigned short int oldMatch = MIN_MATCH - 1;
  52.     int oldOffset;
  53.  
  54.     /*
  55.      * =================================================================
  56.      * Hashes
  57.      * =================================================================
  58.      */
  59. #define StoreHash() ({                                        \
  60.       register struct hashroot *root;                                \
  61.       register int maxcnt;                                    \
  62.                                                 \
  63.       root = &Array[LOOKUP_PREFUNCTION(parseMem)];                        \
  64.       if((maxcnt = root->maxcount)) {                /* begin with 500k + 500k */    \
  65.         register int count, add;                                \
  66.         register struct hashnode *node;                                \
  67.                                                 \
  68.         add = 0;                                        \
  69.         node = root->node;                                    \
  70.         count = node->count;                                    \
  71.         node->entries[count++] = parseMem;            /* register actual match */    \
  72.                                                 \
  73.         if(count > MAX_MATCH) {                                    \
  74.           if((node->entries[count - 1] - node->entries[count - 1 - MAX_MATCH - 1]) == (MAX_MATCH + 1)) {    \
  75.             count--;                                        \
  76.             bcopy(&node->entries[count - MAX_MATCH], &node->entries[count - MAX_MATCH - 1], MAX_MATCH * sizeof(unsigned char *));    \
  77.           }                                            \
  78.         }                                            \
  79.                                                 \
  80.         if(count >= maxcnt) {                    /* expand it */            \
  81.           if(maxcnt < NODES_CLUSTER)                                \
  82.             add = maxcnt;                    /* double size */        \
  83.           else                                            \
  84.             add = NODES_CLUSTER;                                \
  85.         }                                            \
  86.         else if((count > 1) && (count <= (maxcnt >> 1))) {    /* reduce it */            \
  87.           if(maxcnt > NODES_CLUSTER)                                \
  88.             add = -(NODES_CLUSTER);                                \
  89.           else if((maxcnt >>= 1) < NODES_MIN)            /* half size */            \
  90.             add = -(maxcnt - NODES_MIN);                            \
  91.         }                                            \
  92.                                                 \
  93.         if(add) {                                        \
  94.           maxcnt += add;                                    \
  95.           if(!(node = malloc(NODES_SIZE(maxcnt))))                        \                                \
  96.         return ERROR_LESSMEM;                                \
  97.       bcopy(root->node, node, NODES_SIZE(count - NODES_BACKWALL));                \
  98.           free(root->node, NODES_SIZE(root->maxcount));                        \
  99.                                                 \
  100.           root->node = node;                                    \
  101.           root->maxcount = maxcnt;                                \
  102.         }                                            \
  103.         node->count = count;                                    \
  104.       }                                                \
  105.       else {                                            \
  106.         register struct hashnode *node;                                \
  107.                                                     \
  108.         if(!(node = root->node = malloc(NODES_SIZE(NODES_MIN))))                \
  109.       return ERROR_LESSMEM;                                    \
  110.         root->maxcount = NODES_MIN;                                \
  111.         node->count = 1;                                    \
  112.         node->entries[0] = parseMem;                /* register actual match */    \
  113.       }                                                \
  114.     })
  115.  
  116.     /*
  117.      * =================================================================
  118.      * Matches
  119.      * =================================================================
  120.      */
  121. #define    FindMatch() ({                                        \
  122.       while (--tries >= 0) {                                    \
  123.         register unsigned char *beginHist = *--tryhistory;        /* characters after first character */    \
  124.                                                 \
  125.     if (*((unsigned short int *)(beginHist + oldMatch - 1)) ==                \
  126.         *((unsigned short int *)(parseMem  + oldMatch - 1))) {    /* compare with last character */    \
  127.       if (*((unsigned short int *)(beginHist + 1)) ==        /* already verified from hash */    \
  128.           *((unsigned short int *)(parseMem + 1))) {                    \
  129.         /* do not invalidate flowing beginHist and constant beginPars */            \
  130.         register unsigned char *newHist = beginHist + MIN_MATCH;                \
  131.         register unsigned char *newPars = parseMem  + MIN_MATCH;                \
  132.         register int newMatch = MIN_MATCH + 3;        /* first byte allready parsed */    \
  133.                                 /* hopefully execute from left to right */    \
  134.         while (newMatch < (MAX_MATCH + 3)) {        /* do not overflow */        \
  135.           if (*((unsigned int *)newHist)++ !=                        \
  136.           *((unsigned int *)newPars)++) {        /* compare with characters after first character */    \
  137.             break;                                        \
  138.           }                                            \
  139.           newMatch += 4;                                    \
  140.         }                                            \
  141.         if(newMatch > oldMatch) {                                \
  142.           newHist -= 4;                                    \
  143.           newPars -= 4;                                    \
  144.           if (*((unsigned short int *)newHist)++ !=                        \
  145.               *((unsigned short int *)newPars)++) {        /* compare with characters after first character */    \
  146.             newMatch -= 2;                                    \
  147.             newHist -= 2;                                    \
  148.             newPars -= 2;                                    \
  149.           }                                            \
  150.           if (*((unsigned char *)(newHist)) !=                        \
  151.           *((unsigned char *)(newPars))) {        /* compare with characters after first character */    \
  152.             newMatch -= 1;                                    \
  153.           }                                            \
  154.                                                 \
  155.           if (newMatch > oldMatch) {            /* accept if longer than last match */    \
  156.             oldOffset = newHist - newPars;            /* calculate negative offset */    \
  157.             if ((oldMatch = newMatch) >= MAX_MATCH) {    /* correct length if longer than maximal match */    \
  158.           oldMatch = MAX_MATCH;                                \
  159.           break;                    /* do not continue if maximum matchlength reached */    \
  160.             }                                        \
  161.           }                                            \
  162.         }                                            \
  163.       }                                            \
  164.     }                                            \
  165.       }                                                \
  166.     })
  167.  
  168. #define GetHash() ({                                        \
  169.         register struct hashnode *node;                                \
  170.         register int remove;                                    \
  171.                                                 \
  172.         if(!(node = Array[remove = LOOKUP_PREFUNCTION(parseMem)].node)) {            \
  173.           if(!(node = Array[remove].node = malloc(NODES_SIZE(NODES_MIN))))            \
  174.         return ERROR_LESSMEM;                                \
  175.           Array[remove].maxcount = NODES_MIN;                            \
  176.           node->count = 0;                                    \
  177.         }                                            \
  178.         else {                                            \
  179.           register int tries;                                    \
  180.           register unsigned char **tryhistory;                            \
  181.                                                 \
  182.           tries = node->count;                                    \
  183.                                                 \
  184.           for(remove = 0; tries > remove; remove++) {        /* while the history-entries are too big, remove them, thats okay, they are distance-sorted */    \
  185.             if((parseMem - node->entries[remove]) <= (HISTORY_LENGTH))                \
  186.               break;                                        \
  187.           }                                            \
  188.                                                 \
  189.           if(remove) {                        /* streight move the entries from right to left to prevent sorting order */    \
  190.             tries -= remove;                                    \
  191.         bcopy(&node->entries[remove], &node->entries[0], tries * sizeof(unsigned char *));    \
  192.             node->count = tries;                                \
  193.           }                                            \
  194.           tryhistory = &node->entries[tries];                            \
  195.           FindMatch();                                        \
  196.         }                                            \
  197.       })
  198.  
  199. #define GetMatch() ({                                        \
  200.       GetHash();                                        \
  201.     })
  202.  
  203. #define    UpdateIndex() ({                                    \
  204.       if (--indexPos < 0) {                    /* flush index if full */    \
  205.     *indexMem = index;                                    \
  206.     indexMem = ((unsigned int *)pasteMem)++;                        \
  207.     index = 0;                                        \
  208.     indexPos = INDEX_LENGTH - 1;                                \
  209.       }                                                \
  210.                                                 \
  211.       if (pasteMem > outMem)                    /* brute break if destination overflow, TODO: clean break, not abort() */    \
  212.     return ERROR_OVERFLOW;                                    \
  213.     })
  214.  
  215. #define StoreLiteral() ({                                    \
  216.       StoreHash();                                        \
  217.                                                 \
  218.       /* store 8bit literal */                                    \
  219.       *pasteMem++ = *parseMem++;                /* store plain literal */    \
  220.       inSize -= sizeof(unsigned char);            /* reduce number of left bytes */    \
  221.                                                 \
  222.       UpdateIndex();                                        \
  223.     })
  224.  
  225. #define StoreMatch() ({                                        \
  226.       register int setMatch;                                    \
  227.                                                     \
  228.       if (oldMatch > (unsigned short int)inSize)        /* protect against underflow */    \
  229.     oldMatch = (unsigned short int)inSize;                            \
  230.       if ((setMatch = oldMatch - MIN_MATCH) >= 0) {                        \
  231.     register int orIndex;                                    \
  232.                                                 \
  233.     if ((setMatch <= 0x3) && (oldOffset >= 0xFFFFC000)) {                    \
  234.       *((unsigned short int *)pasteMem)++ = (unsigned short int)((((unsigned short int)oldOffset) << 2) | (setMatch));    \
  235.       orIndex = 0x1;                                    \
  236.     }                                            \
  237.     else if ((setMatch <= 0xF) && (oldOffset >= 0xFFFFF000)) {                \
  238.       *((unsigned short int *)pasteMem)++ = (unsigned short int)((((unsigned short int)oldOffset) << 4) | (setMatch));    \
  239.       orIndex = 0x2;                                    \
  240.     }                                            \
  241.     else {                                            \
  242.       /* store 16bit history */                                \
  243.       *((unsigned short int *)pasteMem)++ = (unsigned short int)(oldOffset);        \
  244.       /* store 8bit length */                                \
  245.       *pasteMem++ = (unsigned char)(setMatch);                        \
  246.       orIndex = 0x3;                                    \
  247.     }                                            \
  248.                                                 \
  249.     index |= (orIndex << (indexPos * INDEX_BITS));                        \
  250.       }                                                \
  251.       else {                                            \
  252.     /* store 8bit literal */                                \
  253.     *pasteMem++ = *parseMem;                /* store plain literal */    \
  254.     oldMatch = sizeof(unsigned char);                            \
  255.       }                                                \
  256.                                                 \
  257.       inSize -= oldMatch;                    /* reduce number of left bytes */    \
  258.       /* goto position after valid match */                            \
  259.       for((short int)oldMatch -= 1; (short int)oldMatch >= 0; (short int)oldMatch--) {    /* runs oldMatch - 1 times */    \
  260.     StoreHash();                                        \
  261.     parseMem++;                                        \
  262.       }                                                \
  263.                                                 \
  264.       UpdateIndex();                                        \
  265.     })
  266.  
  267.     /*
  268.      * =================================================================
  269.      * Main-Parsing
  270.      * =================================================================
  271.      */
  272.     GetMatch();                            /* set initial match */
  273.     if (oldMatch < MAX_MATCH) {                    /* try only something better if there could be something longer */
  274.       register unsigned short int k;
  275.       register unsigned short int revMatch = oldMatch;        /* store old state */
  276.       register int revOffset = oldOffset;
  277.  
  278.       for (k = 1; k < Mode; k++) {                /* we leave this loop only if none of the next two tries matches better */
  279.     parseMem++;                        /* try next possible match */
  280.     GetMatch();
  281.  
  282.     if ((oldMatch - k) > revMatch) {            /* match is better, store everything before */
  283.       revMatch = oldMatch;                    /* store new state */
  284.       revOffset = oldOffset;
  285.       parseMem -= k;                    /* jump to beginning of best-match-sliding */
  286.       oldMatch = MIN_MATCH - 1;                /* store them all as literals */
  287.  
  288.       for (; k >= 1; k--)                    /* store every previous try */
  289.         StoreLiteral();
  290.  
  291.       if (revMatch >= MAX_MATCH) {                /* brute break if match reaches maximum */
  292.         k = 1;                        /* don't rewind parseMem if we break the loop */
  293.         break;
  294.       }
  295.     }
  296.       }
  297.  
  298.       parseMem -= (k - 1);                    /* none of the two tries matches better, so rewind both tries (means three bytes) */
  299.       oldOffset = revOffset;                    /* restore old state */
  300.       oldMatch = revMatch;
  301.     }
  302.     StoreMatch();                        /* save last match */
  303.   }
  304.  
  305.   index |= (0x3 << (indexPos * INDEX_BITS));            /* flush index */
  306.   *indexMem = index;                        /* and store */
  307.   *((unsigned short int *)pasteMem)++ = 0;
  308.  
  309.   outSize = pasteMem - (outMem - outSize);            /* get size */
  310.  
  311.   return outSize;
  312. }
  313.